UVa/314 - Robot/314.cpp

   1 /*
   2   Problem: 314 - Robot (UVa)
   3   Author: Andrés Mejía-Posada
   4   (http://blogaritmo.factorcomun.org)
   5
   6 */
   7
   8 using namespace std;
   9 #include <algorithm>
  10 #include <iostream>
  11 #include <iterator>
  12 #include <sstream>
  13 #include <fstream>
  14 #include <cassert>
  15 #include <climits>
  16 #include <cstdlib>
  17 #include <cstring>
  18 #include <string>
  19 #include <cstdio>
  20 #include <vector>
  21 #include <cmath>
  22 #include <queue>
  23 #include <deque>
  24 #include <stack>
  25 #include <map>
  26 #include <set>
  27
  28 #define D(x) cout << #x " is " << x << endl
  29
  30
  31 struct state{
  32   short i, j, d, w;
  33   state(){} state(short i, short j, short d, short w) : i(i), j(j), d(d), w(w) {}
  34 };
  35
  36 int di[] = {-1, +0, +1, +0}, dj[] = {+0, +1, +0, -1};
  37
  38 const int N = 51;
  39
  40 int g[N+1][N+1], t[N+2][N+2], n, m;
  41 bool v[N+1][N+1][4];
  42
  43 void bfs(){
  44   short si, sj, fi, fj; string dir;
  45   cin >> si >> sj >> fi >> fj >> dir;
  46   short sd;
  47   switch (dir[0]){
  48   case 'n': sd = 0; break;
  49   case 'e': sd = 1; break;
  50   case 's': sd = 2; break;
  51   case 'w': sd = 3; break;
  52   }
  53
  54   assert(t[si][sj]);
  55   if (t[fi][fj]){
  56     queue<state> q;
  57     memset(v, 0, sizeof v);
  58     q.push(state(si, sj, sd, 0));
  59     while (q.size()){
  60
  61 #define f q.front()
  62       short i = f.i, j = f.j, d = f.d, w = f.w;
  63 #undef f
  64
  65       q.pop();
  66
  67       if (i < 0 || i > n || j < 0 || j > m || !t[i][j] || v[i][j][d]) continue;
  68
  69       if (i == fi && j == fj){
  70         //printf("popped %d %d %d %d\n",i,j,d,w);
  71         cout << w << endl;
  72         return;
  73       }
  74
  75       //printf("popped %d %d %d %d\n",i,j,d,w);
  76       v[i][j][d] = true;
  77
  78       q.push(state(i, j, (d+1)%4, w+1));
  79       q.push(state(i, j, (d+3)%4, w+1));
  80       for (int k=1; k<=3; ++k){
  81         int ni = i+k*di[d], nj = j+k*dj[d];
  82         if (ni < 0 || ni > n || nj < 0 || nj > m || !t[ni][nj]) break;
  83         q.push(state(ni, nj, d, w+1));
  84       }
  85
  86     }
  87   }
  88   cout << "-1\n";
  89 }
  90
  91 int main(){
  92   while (cin >> n >> m && (n+m)){
  93     for (int i=0; i<n; ++i){
  94       for (int j=0; j<m; ++j){
  95         cin >> g[i][j];
  96       }
  97     }
  98
  99     //Crear matriz t(ransformada)
 100     for (int i=0; i<=n; ++i){
 101       for (int j=0; j<=m; ++j){
 102         if (i == 0 || j == 0 || i == n || j == m) t[i][j] = 0;
 103         else t[i][j] = !g[i-1][j-1] && !g[i-1][j] && !g[i][j-1] && !g[i][j];
 104         //cout << t[i][j] << " ";
 105       }
 106       //cout << endl;
 107
 108     }
 109
 110     //Hacer BFS sobre t
 111     bfs();
 112   }
 113   return 0;
 114 }